package Merger;

import java.util.Random;

/**
 * Created with IntelliJ IDEA.
 * User: lysergid
 * Date: 24.10.13
 * Time: 22:22
 * To change this template use File | Settings | File Templates.
 */
public class MergeSorter extends SomeSorter {
    private static final int START_INDEX = 0;
    public static int intsInMemory;
    public static int comparations;

    @Override
    public int[] sort(int[] arrayToSort) {
        return divideToParts(arrayToSort);
    }

    private int[] divideToParts(int[] arrayToSort) {
        int middle = arrayToSort.length / 2;
        int[] leftArray = new int[middle];
        int[] rigthArray = new int[arrayToSort.length - middle];
        int[] result = new int[arrayToSort.length];

        if (arrayToSort.length <= 1) {
            return arrayToSort;
        } else {


            System.arraycopy(arrayToSort, START_INDEX, leftArray, START_INDEX, middle);// copy left part of source array to another
            System.arraycopy(arrayToSort, middle, rigthArray, START_INDEX, rigthArray.length);// copy rigth part of source array to another

            leftArray = divideToParts(leftArray);
            rigthArray = divideToParts(rigthArray);

            result = mergeParts(leftArray, rigthArray);
        }
        oneMoreInt(leftArray.length + rigthArray.length + result.length);
        return result;
    }

    private int[] mergeParts(int[] leftArray, int[] rigthArray) {

        int[] result = new int[leftArray.length + rigthArray.length];
        int resultLength = result.length;
        int rigthIndex = 0;
        int leftIndex = 0;
        int resultIndex = 0;

        while (resultLength > resultIndex) {

            if (leftIndex < leftArray.length) {

                if (rigthIndex >= rigthArray.length) {
                    result[resultIndex] = leftArray[leftIndex];
                    leftIndex++;
                    resultIndex++;

                } else if (rigthArray[rigthIndex] > leftArray[leftIndex]) {

                    oneMoreCorporation();

                    result[resultIndex] = leftArray[leftIndex];
                    leftIndex++;
                    resultIndex++;
                }
            }

            if (rigthIndex < rigthArray.length) {

                if (leftIndex >= leftArray.length) {
                    result[resultIndex] = rigthArray[rigthIndex];
                    rigthIndex++;
                    resultIndex++;


                } else if (rigthArray[rigthIndex] < leftArray[leftIndex]) {

                    oneMoreCorporation();

                    result[resultIndex] = rigthArray[rigthIndex];
                    rigthIndex++;
                    resultIndex++;
                }
            }
        }

        return result;
    }

    private void oneMoreInt(int howMuchInts) {
        for (int i = 0; i < howMuchInts; i++) {
            intsInMemory++;
        }
    }

    private void oneMoreCorporation() {
        comparations++;
    }
}
